'''
在计数排序中,如果元素的范围比较大(比如1到1亿之间),如何改造算法
桶排序(bucket sort):首先将元素分在不同的桶中,在对每个桶中的元素排序

'''
def bucket_sort(li,n=100,max_num=10000):
    buckets = [[] for _ in range(n)] # 创建桶(一个二维列表)
    for var in li:
        i = min(var // (max_num // n),n-1) # i表示var放在i号桶里
        buckets[i].append(var)
        for j in range(len(buckets[i])-1,0,-1): # 遍历子列表中的元素,因为append是从最后添加一个,所以要从最后开始遍历
            if buckets[i][j] < buckets[i][j-1]:  # 对子列表使用冒泡排序
                buckets[i][j],buckets[i][j-1] = buckets[i][j-1],buckets[i][j]
            else:
                break
    sorted_li = []
    for buck in buckets:
        sorted_li.extend(buck)
    return sorted_li

import random
li = [random.randint(0,10000) for i in range(100000)]
print(li)
li = bucket_sort(li)
print(li)